package com.lft.ten_commonly_used_algorithms01.binary_search;

/**
 * 二分查找算法（递归实现）
 */
public class BinarySearchRecursion {
	public static void main(String[] args) {
		// 前提条件，有序号数组。
		int[] array = {1, 3, 8, 10, 11, 67, 100};
		int index = binarySearchRecursion(array, 100, 0, array.length - 1);
		System.out.println(index);
	}
	
	/**
	 * 二分查找算法
	 * @param array  待查找的有序（升序）数组
	 * @param target 要查找的数。
	 * @return 返回对应下标。未找到返回 -1
	 */
	public static int binarySearchRecursion(int[] array, int target, int left, int right) {
		if (left > right || target < array[0] || target > array[array.length - 1]) {
			return -1;
		}
		int mid = (left + right) / 2;
		if (array[mid] == target) {
			return mid;
		} else if (array[mid] > target) {
			return binarySearchRecursion(array, target, left, mid - 1);
		} else {
			return binarySearchRecursion(array, target, mid + 1, right);
		}
	}
}
